#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/11/5 09:34
# @Author  : jackkli
# @Site    : 
# @File    : 076color_ classification.py
# @Software: PyCharm
"""
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

"""


def sort_colors(nums):
    """
    :type nums: List[int]
    :rtype: None Do not return anything, modify nums in-place instead.
    """
    n = len(nums)
    a = 0
    for i in range(n):
        if nums[i] == 0:
            nums[i], nums[a] = nums[a], nums[i]
            a += 1
        print("i={},a={}".format(i, a))
        print("nums:{}".format(nums))
    for i in range(a, n):
        if nums[i] == 1:
            nums[i], nums[a] = nums[a], nums[i]
            a += 1
        print("i={},a={}".format(i, a))
        print("nums:{}".format(nums))


def fun_sort(nums):
    a = 0
    b = len(nums) - 1
    i = 0
    while i <= b:
        while nums[i] == 2 and i <= b:
            nums[i], nums[b] = nums[b], nums[i]
            b -= 1
            print("i={},a={},b={}".format(i, a, b))
            print("nums:{}".format(nums))
        if nums[i] == 0:
            nums[i], nums[a] = nums[a], nums[i]
            a += 1
        i += 1


if __name__ == '__main__':
    # num = [2, 0, 1]
    num = [2, 1, 2]
    # sort_colors(nums=num)
    fun_sort(nums=num)
    # print(sorted(num))
